package xio.ccf_201809;

import java.util.*;

/**
 * ccf 20180904
 * 再卖菜 100分
 *
 * 此题是一道差分约束的问题，我们用单源最短路径来求解；
 * 关于差分约束，以及其解法，可以参考《算法导论》24.4 内容
 * ------ 本题思路  ---------
 *  首先根据本题题意，假设第一天的价格为 a1,a2,...an ,第二天价格为 b1,b2...bn；
 *  其需要满足条件：
 *      1.每天的价格 >= 1
 *      2. 由于第二天的价格为前一天相邻店铺价格的平均值的去尾值，因此，
 *      (ai + aj + ak)/3 - bj <= 2/3
 *      (a1 + a2)/2 - b1 <= 1/2
 *
 *   由此，可以得到差分不等式为：
 *      0<= (a1+a2)/2 - b1 <= 1/2
 *      0<= (a1+a2+a3)/3 - b2 <= 2/3
 *      0<= (a2+a3+a4)/3 - b3 <= 2/3
 *      ...
 *
 *      以及
 *      a1 >= 1
 *      a2 >= 1
 *      ...
 *
 *      上面的差分不等式出现了三元未知数的情况，我们需要转化为二元的形式才能构造图来求解。我们将第一天前 i 天的价格记为 Si = a1 + a2 + ... + ai，且S0 = 0，则：
 *      上面的不等式可以变为（统一变成大于等于的形式）：
 *
 *       S2 - S0  >= 2b1
 *       S0 - S2  >= -(2b1 + 1)
 *       S3 - S0  >= 3b2
 *       S0 - S3  >= -(3b2 + 2)
 *       S4 - S1  >= 3b3
 *       S1 - S4  >= -(3b3 + 2)
 *        ...
 *
 *       以及
 *       S1 - S0 >= 1
 *       S2 - S1 >= 1
 *       ...
 *
 *      以 S0为源点，S1,S2...Sn 为各节点来构造有向图，最后走最长路径来求即可。
 *
 */
public class VegetablesSellAgain {
    public static void main(String[] args) {

        // 读取输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] prices = new int[n+1];

        for (int i = 1; i < n+1; i++) {
            prices[i] = sc.nextInt();
        }

        // 构建图
        Graph g = new Graph(n);

        for (int i = 0; i < n-2; i++) {
            g.addEdge(i+3,i,-(prices[i+2]*3+2));
            g.addEdge(i,i+3,prices[i+2]*3);
        }
        g.addEdge(2,0,-(prices[1]*2+1));g.addEdge(0,2,prices[1]*2);   //对开始两个单独处理
        g.addEdge(n,n-2,-(prices[n]*2+1));g.addEdge(n-2,n,prices[n]*2);  //对结尾两个单独处理
        for (int i = 1; i < n+1; i++) {
            g.addEdge(i-1,i,1);              //每个数都要大于等于1
        }
        // 开始路径搜索
        g.sfpa();


        // 输出结果
        for (int i = 1; i < n + 1; i++) {
            int r = g.dist[i]-g.dist[i-1];
            System.out.print(r+" ");
        }


    }

    static class Graph{
        // 邻接图
        List<LinkedHashSet<Edge>> adj;
        // N 个节点
        int N;
        // 源点到各节点的最长路径
        int[] dist;

        public Graph(int N){
            this.N = N;

            dist = new int[N+1];
            adj = new ArrayList<>();
            for (int i = 0; i < N+1; i++) {
                LinkedHashSet<Edge> s = new LinkedHashSet<>();
                adj.add(s);
            }
        }
        void addEdge(int x,int y,int v){
            adj.get(x).add(new Edge(y,v));
        }

        void sfpa(){
            LinkedList<Integer> queue = new LinkedList<>();
            for (int i = 0; i < N+1; i++) {
                queue.add(i);
            }

            while (!queue.isEmpty()){
                Integer x = queue.poll();
                for (Edge e : adj.get(x)) {
                    int nx=e.to;
                    if(dist[nx]<dist[x]+e.v) {
                        dist[nx]=dist[x]+e.v;
                        queue.add(nx);
                    }
                }
            }
        }
    }


    static class Edge{
        int to; // 目标节点
        int v; // 边的权重

        Edge(int to, int v) {
            this.to = to;
            this.v = v;
        }
    }
}
